package Demo5;
import java.util.*;
public class Solution {
    //1.验证回文串 II(双指针)
    public boolean validPalindrome(String s) {
        //双指针
        int left = 0;
        int right =s.length() - 1;
        while(left < right){
            if(s.charAt(left) != s.charAt(right)){
                return submit(s, left + 1, right) || submit(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }
    //无非就是[left, right - 1]或者[left + 1, right]
    private boolean submit(String s, int left, int right){
        while(left < right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    //2.重复的子字符串
    public boolean repeatedSubstringPattern(String s) {
        //只需要将两个字符串拼接在一起，去掉头和尾，检验是否包含自身的字串
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);
    }
    //3.字符串中的单词数(双指针)
    public int countSegments(String s) {
        //双指针
        int left = 0;
        int right = 0;
        int count = 0;//计数器
        while(right < s.length()){
            //若碰到的是空格两个指针一起走
            if(s.charAt(right) == ' ' || right + 1 == s.length()){
                //但如果此时left还是指向字母，说明是一个单词
                if(s.charAt(left) != ' '){
                    count++;
                }
                right++;
                left = right;
            }else{
                //是字母
                right++;
            }
        }
        return count;
    }
    //4.删除最外层的括号(辅助栈)
    public String removeOuterParentheses(String s) {
        //思路：遍历，将元素进栈，若栈不为空，则将元素放入，若为空则不放入
        StringBuilder ret = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == ')'){
                stack.pop();
            }
            if(!stack.empty()){
                ret.append(ch);
            }
            if(ch == '('){
                stack.push(ch);
            }
        }
        return ret.toString();
    }
    //5.Excel表列名称(进制)
    public String convertToTitle(int columnNumber) {
        //可以当成10进制来看，这里实际上就是26进制
        //136
        StringBuilder ret = new StringBuilder();
        while(columnNumber > 0){
            columnNumber--;
            char ch = (char)(columnNumber % 26 + 'A');
            ret.append(ch);
            columnNumber /= 26;
        }
        return ret.reverse().toString();
    }
    //6.拼写单词(哈希表)
    public int countCharacters(String[] words, String chars) {
        //哈希表
        int count = 0;
        for(int i = 0; i < words.length; i++){
            Map<Character, Integer> hash = new HashMap<>();
            //统计并计数
            for(int j = 0; j < chars.length(); j++){
                char ch = chars.charAt(j);
                if(!hash.containsKey(ch)){
                    hash.put(ch, 1);
                }else{
                    hash.put(ch, hash.get(ch) + 1);
                }
            }
            //对比
            boolean flag = false;
            for(int k = 0; k < words[i].length(); k++){
                char ch = words[i].charAt(k);
                if(!hash.containsKey(ch)){
                    flag = true;
                    break;
                }else{
                    hash.put(ch, hash.get(ch) - 1);
                }
                if(hash.get(ch) < 0){
                    flag = true;
                    break;
                }
            }
            if(!flag){
                count += words[i].length();
            }
        }
        return count;
    }
    //7.前K个高频单词(top-k + 哈希表)
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> hash = new HashMap<>();
        //统计数量
        for(int i = 0; i < words.length; i++){
            if(!hash.containsKey(words[i])){
                hash.put(words[i], 1);
            }else{
                hash.put(words[i], hash.get(words[i]) + 1);
            }
        }
        //建立小根堆
        PriorityQueue<String> priorityQueue = new PriorityQueue<>(new Comparator<String>() {
            public int compare(String s1, String s2) {
                if (hash.get(s1).equals(hash.get(s2))) {
                    return s2.compareTo(s1);
                } else {
                    return hash.get(s1) - hash.get(s2);
                }
            }
        });
        for(String key : hash.keySet()){
            priorityQueue.offer(key);
            if(priorityQueue.size() > k){
                priorityQueue.poll();
            }
        }
        List<String> ret = new ArrayList<>();
        while(!priorityQueue.isEmpty()){
            ret.add(priorityQueue.poll());
        }
        Collections.reverse(ret);
        return ret;
    }
    //8.IP 地址无效化(哈希)
    public String defangIPaddr(String address) {
        //新数组法
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < address.length(); i++){
            char ch = address.charAt(i);
            if(ch == '.'){
                ret.append("[.]");
            }else{
                ret.append(ch);
            }
        }
        return ret.toString();
    }
    //9.Fizz Buzz(无脑)
    public List<String> fizzBuzz(int n) {
        List<String> ret = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            if(i % 3 == 0 && i % 5 == 0){
                ret.add("FizzBuzz");
            }else if(i % 3 == 0){
                ret.add("Fizz");
            }else if(i % 5 == 0){
                ret.add("Buzz");
            }else{
                String str = String.valueOf(i);
                ret.add(str);
            }
        }
        return ret;
    }
    //10.字符的最短距离(两次遍历)
    public int[] shortestToChar(String s, char c) {
        //思路：两次遍历，一遍从左往右，另一遍从右往左，最后留下小的
        int len = s.length();
        int ret[] = new int[len];
        int ans = Integer.MAX_VALUE;//每次记录下标
        boolean flag = false;//是否已经遇到过目标
        for(int i = 0; i < len; i++){
            if(s.charAt(i) != c && !flag){
                ret[i] = ans--;
            }else if(s.charAt(i) == c){
                ans = 0;
                flag = true;
            }else{
                ret[i] = ++ans;
            }
        }
        flag = false;
        ans = Integer.MAX_VALUE;
        for(int i = len - 1; i >= 0; i--){
            if(s.charAt(i) != c && !flag){
                ret[i] = ans < ret[i] ? ans : ret[i];
                ans--;
            }else if(s.charAt(i) == c){
                ans = 0;
                flag = true;
            }else{
                ans++;
                ret[i] = ans < ret[i] ? ans : ret[i];
            }
        }
        return ret;
    }

}
